'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-01 10:15:37
'''
#
# @lc app=leetcode.cn id=139 lang=python3
#
# [139] 单词拆分
#

# @lc code=start
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict:
            return False
        wordDict = set(wordDict)
        dp = [False]*(len(s)+1)
        dp[0] = True
        # print(wordDict)
        maxx = max([len(i) for i in wordDict])
        for i in range(len(s)):
            tmp = min(i, maxx)
            for j in range(tmp+1):
                if s[i-j:i+1] in wordDict:
                    # print(s[i-j:i+1], i, j)
                    dp[i+1] = dp[i+1] or dp[i-j]
                    # print(dp[i+1], dp[i-j])
        # print(dp)
        return dp[-1] 
# @lc code=end

